package 题目集.动态规划.背包问题;

import java.util.Scanner;

/**
 * https://www.luogu.com.cn/problem/P1776 原本每种货物都有三种属性：重量w，价值v，个数c。
 * 我们可以把每个种类不同个数的货物看城一种货物，例如货物i，重量为3，价值为5，个数为13 我们可以将这个货物看成以下几种货物的组合：
 * 货物i1：重量为3，价值为5。（相当于1个i货物） 货物i2：重量为6，价值为10。（相当于2个i货物）
 * 货物i3：重量为12，价值为20。（相当于4个i货物）
 * 货物i4:重量为18，价值为60。（相当于6个i货物,(这里不能是8个，如果是8个的话会导致i货物的数量比原先多)）
 * 无论选多少个i货物，都可以通过以上货物组合得到，既不会漏掉，也不会多算。 这样就把原本多重背包问题转化为01背包问题。
 */
public class ch09_多重背包2_二进制分解 {
	static int maxN = (int) (1e4 + 10);
	static int[][] info = new int[2][maxN]; // 只存重量和价值
	static int n, cnt, sum; // cnt是根据分组后得出的总数

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		sum = sc.nextInt();
		for (int i = 1; i <= n; i++) {
			int v = sc.nextInt();
			int w = sc.nextInt();
			int c = sc.nextInt();
//			int pow = c / 2;
//			int k = 1;
//			for (; k <= pow; k <<= 1) {
//				cnt++;
//				info[0][cnt] = w * k;
//				info[1][cnt] = v * k;
//			}
//			k--;	//k--是所有合法的k的总和
//			if (c - k > 0) {
//				cnt++;
//				info[0][cnt] = w * (c - k);
//				info[1][cnt] = v * (c - k);
//			}
			//更优的写法
			for (int k = 1; k <= c; k = k << 1) {
				cnt++;
				info[0][cnt] = w * k;
				info[1][cnt] = v * k;
				c -= k;	//由低到高移除k
			}
			if (c > 0) {
				cnt++;
				info[0][cnt] = c * w;
				info[1][cnt] = c * v;
			}
		}
		int res = dp(cnt, sum);
		System.out.println(res);
	}

	public static int dp(int n, int sum) {
		int[][] dp = new int[2][sum + 1];
		int pre, cur = 0;
		for (int i = 1; i <= n; i++) {
			pre = cur;
			cur = (cur + 1) % 2;
			dp[cur][0] = 0;
			for (int j = 1; j <= sum; j++) {
				dp[cur][j] = dp[pre][j];
				if (j >= info[0][i]) {
					dp[cur][j] = Math.max(dp[cur][j], dp[pre][j - info[0][i]] + info[1][i]);
				}
			}
		}
		return dp[cur][sum];
	}
}
